package 动态规划专项训练.动态规划训练1;

/**338. 比特位计数
 * 序列+位操作型动态规划
 * @author zx
 * @create 2022-03-31 20:43
 */
public class Offer090 {
    public int[] countBits(int n) {
        int[] f = new int[n + 1];
        f[0] = 0;
        for(int i = 1;i <= n;i++){
            f[i] = f[i >> 1] + (i % 2);
        }
        return f;
    }
}
